import Nodess from './nodes'
import {Compare,defaultCompare} from './util'
export class BinarySearchTree{
  constructor(compareFn = defaultCompare){
    this.compareFn = compareFn
    this.root = null;
  }

  // 插入节点 
  insert(key){
    if (this.root == null) {
      this.root = new Nodess(key);
    } else {
      this.insertNode(this.root, key);
    }
  }

  //插入树的辅助函数
  insertNode(node,key){
    if(this.compareFn(key,node.key) === Compare.LESS_THAN){
      if(node.left === null){
        node.left = new Nodess(key)
      } else {
        this.insertNode(node.left,key)
      }
    } else {
      if(node.right === null){
        node.right = new Nodess(key)
      } else {
        this.insertNode(node.right,key)
      }
    }
  }

  //中序遍历
  inOrderTraverse(callback){
    this.inOrderTraverseNode(this.root,callback)
  }
  inOrderTraverseNode(node,callback){
    if(node!==null){
      this.inOrderTraverseNode(node.left,callback)
      callback(node.key)
      this.inOrderTraverseNode(node.right,callback)
    }
  }

  //先序遍历
  perOrderTraverse(callback){
    this.perOrderTraverseNode(this.root,callback)
  }
  perOrderTraverseNode(node,callback){
    if(node!==null){
      callback(node.key)
      this.perOrderTraverseNode(node.left,callback)
      this.perOrderTraverseNode(node.right,callback)
    }
  }

  //后序遍历
  postOrderTraverse(callback){
    this.postOrderTraverseNode(this.root,callback)
  }
  postOrderTraverseNode(node,callback){
    if(node!==null){
      this.postOrderTraverseNode(node.left,callback)
      this.postOrderTraverseNode(node.right,callback)
      callback(node.key)
    }
  }

  //搜索树中的最小值
  min(){
    return this.minNode(this.root)
  }
  //搜索最小值辅助函数
  minNode(node){
    let current = node
    while(current!==null && current.left!==null){
      current = current.left
    }
    return current
  }

  //搜索树中的最大值
  max(){
    return this.maxNode(this.root)
  }
  //搜索最在值辅助函数
  maxNode(node){
    let current = node
    while(current!==null && current.right!==null){
      current = current.right
    }
    return current
  }

  // 搜索特定值
  search(key){
    return this.searchNode(this.root,key)
  }
  //搜索特定值辅助函数
  searchNode(node,key){
    if(node === null){
      return false;
    }
    if(this.compareFn(key,node.key) === Compare.LESS_THAN){
      return this.searchNode(node.left,key)
    } else if(this.compareFn(key,node.key) === Compare.BIGGER_THAN){
      return this.searchNode(node.right,key)
    } else {
      return true
    }
  }

  //移除指定节点
  remove(key){
    this.root = this.removeNode(this.root,key)
  }
  removeNode(node,key){
    if(node === null){
      return null;
    }
    if(this.compareFn(key,node.key) === Compare.LESS_THAN){
      node.left = this.removeNode(node.left,key);
      return node;
    } else if(this.compareFn(key,node.key) === Compare.BIGGER_THAN){
      node.right = this.removeNode(node.right,key)
      return node;
    } else {
      if(node.left === null && node.right === null){
        node = null
        return node;
      }
      if(node.left === null){
        node = node.right;
        return node;
      } else if(node.right === null) {
        node = node.left
        return node;
      }

      const aux = this.minNode(node.right);
      node.key = aux.key
      
      node.right = this.removeNode(node.right,aux.key);
      return node;
    }
  }
}


let sq = new BinarySearchTree()
// console.log(sq)
sq.insert(11)
sq.insert(7)
sq.insert(15)
sq.insert(3)
sq.insert(9)
sq.insert(8)
sq.insert(10)
sq.insert(13)
sq.insert(12)
sq.insert(14)
sq.insert(20)
sq.insert(18)
sq.insert(25)
// console.log(sq)
// const printNode = (val) => console.log(val)

// sq.inOrderTraverse(printNode)
// sq.perOrderTraverse(printNode)
// sq.postOrderTraverse(printNode)
// console.log(sq.search(132))
// sq.remove(15)
// console.log(sq)